package 动态规划;

/**
 * 给定一个字符串 s，请将 s 分割成一些子串，使每个子串都是回文串。
 * 返回符合要求的 最少分割次数 。
 *
 * 状态定义：F(i): s 的前 i 个字符最小的分割次数
 * 状态转移方程：
 *         F(i): j < i && [j + 1, i]是回文串: min(F(j)) + 1
 *         F(i): [1,i]是回文串：0
 * 状态初始化：
 *         F(i): i-1  每一个长度的子串的最大分割次数都是i-1
 * 返回结果：
 *         F(i) =
 */
public class 剑指offer94_最少回文分割 {
    public int minCut(String s) {
        int len = s.length();
        if(len == 0) {
            return 0;
        }
        if (isPalindrome(s,0,len-1)) {
            return 0;
        }
        int[] minCut = new int[len+1];
        for (int i = 1; i <= len; i++) {
            minCut[i] = i-1;
        }
        for (int i = 2; i <= len; i++) {
            // 整体是否是回文串
            if(isPalindrome(s,0,i-1)) {
                minCut[i] = 0;
                continue;
            }
            for (int j = 1; j < i; j++) {
                // j < i && [j + 1, i]是回文串: min(F(j) + 1
                if(isPalindrome(s,j,i-1)) {
                    minCut[i] = Math.min(minCut[i],minCut[j]+1);
                }
            }
        }
        return minCut[len];
    }
    public boolean isPalindrome(String s,int start, int end) {
        char[] str = s.toCharArray();
        while (start < end) {
            if(str[start] != str[end]) {
                return false;
            }
        }
        return true;
    }

}
//    StringBuffer str = new StringBuffer();
//        for(int i = srart; i <= end; i++) {
//        char ch = s.charAt(i);
//        if(Character.isLetterOrDigit(ch)) {
//            str.append(Character.toLowerCase(ch));
//        }
//    }
//    int length = str.length();
//    int left = 0;
//    int right = length - 1;
//        while(left < right) {
//        if(Character.toLowerCase(str.charAt(left)) != Character.toLowerCase(str.charAt(right))) {
//            return false;
//        }
//        left++;
//        right--;
//    }
//        return true;

